package com.atguigu.main.sort;

import java.util.Arrays;

/**
 * @author ：剧情再美终是戏
 * @description：快速排序实现
 * @mail : 13286520398@163.com
 * @date ：Created in 2020/2/28 20:26
 * @modified By：
 * @version: 1.0$
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {2, 8, 7, 1, 3, 5, 6, 4};
        quicksort(arr, 0, 7);
        System.out.println(Arrays.toString(arr));
    }

    public static void quicksort(int[] arr, int l, int r) {
        // 参数过滤
        if (l < r) {
            // 计算哨兵，这个过程获取一个中位数出来
            int p = getPartition(arr, l, r);
            // 以哨兵为分界线，递归排序左边的数据
            quicksort(arr, l, p - 1);
            // 以哨兵为分界线，递归排序右边的数据
            quicksort(arr, p + 1, r);
        }
    }

    // 2, 8, 7, 1, 3, 5, 6, 4
    private static int getPartition(int[] arr, int l, int r) {
        int x = arr[r];
        int i = l - 1;
        for (int j = l; j < r; j++) {
            if (arr[j] >= x) { // 如果发现有数据比定义的右边界值大，就将 i + 1, 交换 i j 之间的值 <= 就是升序排序
                i += 1;
                swap(arr, i, j);
            }
        }
        // i + 1 跟 r 交换位置
        swap(arr, i + 1, r);
        // 返回 i + 1 的位置，就是哨兵的位置
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
